package lizhe.dummynode;

import lizhe.dummynode.ListNode;

public class ReverseList {
    public static ListNode reverseList(ListNode head) {

        ListNode a = head;
        ListNode b = null;
        ListNode c = null;

        while (a != null) {
            c = a;
            a = a.next;
            c.next = b;
            b = c;
        }
        return b;
    }
    public static ListNode reverseList2(ListNode head) {

        return reverse(head,null);
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        head.next = listNode2;
        ListNode listNode3 = new ListNode(3);
        listNode2.next = listNode3;
        ListNode listNode4 = new ListNode(4);
        listNode3.next = listNode4;
        ListNode listNode5 = new ListNode(5);
        listNode4.next = listNode5;

        reverseList(head);
    }

    private static ListNode reverse(ListNode head, ListNode newHead) {
        if (head == null) {
            return newHead;
        }
        ListNode next = head.next;
        head.next = newHead;
        return reverse(next, head);
    }

    //迭代 递归
}
